#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020/7/12 19:23|19:23
# @Author  : yangdingyi
# @File    : 2020-07-12.3.5211. 概率最大的路径
# @Software: PyCharm
from typing import List


class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        if not edges:
            return 0.0
        le = len(edges)
        ans = [0.0 for i in range(n)]
        ans[start] = 1.0
        for i in range(n):
            flag = True
            for j in range(le):
                s, e = edges[j][0], edges[j][1]
                if ans[s] * succProb[j] > ans[e]:
                    ans[e] = ans[s] * succProb[j]
                    flag = False
                if ans[e] * succProb[j] > ans[s]:
                    ans[s] = ans[e] * succProb[j]
                    flag = False
            if flag:
                break
        return ans[end]


solve = Solution()

questions = [
    (3, [[0, 1], [1, 2], [0, 2]], [0.5, 0.5, 0.2], 0, 2),
    (5, [[1, 4], [2, 4], [0, 4], [0, 3], [0, 2], [2, 3]], [0.37, 0.17, 0.93, 0.23, 0.39, 0.04], 3, 4),
]

for qi, q in enumerate(questions):
    print(f'#{qi}:', q)
    print('ans:', solve.maxProbability(q[0], q[1], q[2], q[3], q[4]))
